package leetcode;

import java.util.HashMap;

import dataStrcture.UnionFind;

public class EvaluateDivision {

    public static void main(String[] args) {

    }

    private static class UF<T> {
        HashMap<T, T> id;
        // 表示某一个集合里的大小
        int[] size;

        int index = 0;

        public UF(int n) {
            id = new HashMap<>();
            size = new int[n];
            for (int i = 0; i < n; i++) {
                size[i] = 1;
            }
        }

        private T find(T p) {
            T group = id.get(p);
            return group == null ? null : find(group);
        }

        public void union(T p, T q) {
            T pId = find(p);
            T qId = find(p);
            if (pId == null) {
                id.put(p, p);
                pId = p;
            }
            if (qId == null) {
                id.put(q, q);
                qId = q;
            }
            if (pId.equals(qId)) {
                return;
            }

            id.put(pId, qId);
//            if (size[pId] < size[qId]) {
//                size[qId] += size[pId];
//            } else {
//                id.put(q, pId);
//                size[pId] += size[qId];
//            }
        }

        public boolean isUnion(T p, T q) {
            T pId = find(p);
            T qId = find(p);
            return pId != null && pId.equals(qId);
        }
    }

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        UF<String> unionFind = new UF<>(values.length * 2);
        for (int i = 0; i < equations.length; i++) {
            String a = equations[i][0];
            String b = equations[i][1];
            unionFind.union(a, b);
        }
        for (int i = 0; i < queries.length; i++) {

        }
        return null;
    }

}
